import java.util.ArrayList;
import java.util.List;

public class Solution57 {
    public int[][] insert(int[][] intervals, int[] newInterval) {
        List<int[]> res = new ArrayList<>();
        int max = -1;
        boolean flag = false;
        if (intervals.length == 0) {
            res.add(newInterval);
            flag = true;
            max = res.get(0)[1];
        }
        for (int[] interval : intervals) {
            if (!flag && interval[0] > newInterval[0]) {
                if (newInterval[0] > max) {
                    res.add(newInterval);
                }
                flag = true;
                max = Math.max(max, newInterval[1]);
                res.get(res.size() - 1)[1] = max;
            }
            if (interval[0] <= max) {
                max = Math.max(max, interval[1]);
                res.get(res.size() - 1)[1] = max;
            } else {
                res.add(interval);
                max = interval[1];
            }
        }
        if (!flag) {
            if (newInterval[0] > max) {
                res.add(newInterval);
            }
            max = Math.max(max, newInterval[1]);
            res.get(res.size() - 1)[1] = max;
        }
        return res.toArray(new int[res.size()][]);
    }
}
